﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<string.h>
#include<stdlib.h>

//void GetMemory(char** p, int num)
//{
//	*p = (char*)malloc(num);
//}
//void Test(void)
//{
//	char* str = NULL;
//	GetMemory(&str, 100);
//	strcpy(str, "hello");
//	printf(str);
//}
//int main()
//{
//	Test();
//	return 0;
//}


//求容积最大值  1；
#include<stdlib.h>
//int cmp(const void* e1,const void* e2)
//{
//    return *(int*)e2 - *(int*)e1;
//}
//int findindex(int* height, int heightSize)
//{
//    int min = 10000;
//    int minindex = -1;
//    for (int i = 0; i < heightSize; i++)
//    {
//        if (height[i] != 0 && height[i] < min)
//        {
//            min = height[i];
//            minindex = i;
//        }
//    }
//    return minindex;
//}
//int maxArea(int* height, int heightSize) {
//    int area = 0;;
//
//    int num = 0;
//    while (num < heightSize)
//    {
//        int index = findindex(height, heightSize);
//        int i = 0;
//        int j = heightSize - 1;
//        if (i + j > 2 * index)
//        {
//            while (j > index)
//            {
//                if (height[j] != 0)
//                {
//                    if ((j - index) * height[index] > area)
//                    {
//                        area = (j - index) * height[index];
//                        
//                        
//                    }
//                    break;
//                }
//                j--;
//            }
//        }
//        else
//        {
//            while (i < index)
//            {
//                if (height[i] != 0)
//                {
//                    if ((index - i) * height[index] > area)
//                    {
//                        area = (index -i) * height[index];
//
//                        
//                    }
//                    break;
//
//                }
//                
//                i++;
//            }
//        }
//        num++;
//        height[index] = 0;
//    }
//      return area;
//}

//2:双指针

int maxArea(int* height, int heightSize) {
    if (heightSize == 1)
        return 0;
    if (heightSize == 2)
        return height[0] < height[1] ? height[0] : height[1];
    int area = 0;
    int i = 0;
    int j = heightSize - 1;
    int min = 0;
    while (i < j)
    {
        int ret1 = j - i;
        if (height[i] < height[j])
        {
            min = height[i];

            i++;

        }
        else
        {
            min = height[j];
            j--;
        }
        int ret = ret1 * min;
        if (ret > area)
        {
            area = ret;
        }

    }


    return area;
}




//求最长回文子串
//#include<string.h>
//char* longestPalindrome(char* s) {
//    int stringlen = strlen(s);
//    int i = 0;
//    int j = stringlen - 1;
//    int len = 0;
//    char* p = NULL;
//    int index = 0;
//    for (; i < stringlen; i++)
//    {
//        for (j = stringlen - 1; j >= i; j--)
//        {
//            if (s[j] == s[i])
//            {
//                int reti = i;
//                int retj = j;
//                int num = 0;
//                while (reti < retj && s[reti] == s[retj])
//                {
//                    reti++, retj--;
//                    num += 2;
//                }
//                if (retj == reti)
//                {
//                    num++;
//                }
//                else if (retj < reti)
//                {
//                    ;
//                }
//                else
//                {
//                    continue;
//                }
//                if (num > len)
//                {
//                    p = &s[i];
//                    index = j + 1;
//                    len = num;
//                }
//
//            }
//            else
//            {
//                continue;
//            }
//        }
//    }
//    s[index] = 0;
//    return p;
//}
//
//int main()
//{
//    int height[] = { 1,8,6,2,5,4,8,3,7 };
//    int heightSize = 9;
//    int x = maxArea(height, heightSize);
//    printf("%d", x);
//
//    return 0;
//}


//将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。
//
//比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：
//
//P   A   H   N
//A P L S I I G
//Y   I   R
//之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。
//
//请你实现这个将字符串进行指定行数变换的函数：
//
//string convert(string s, int numRows);

//#include<string.h>
//char* convert(char* s, int numRows) {
//    int len = strlen(s);
//    char* p = (char*)calloc(len + 1, 1);
//    if (p != NULL)
//    {
//        if (len < numRows || numRows == 1)
//        {
//            strncat(p, s, len);
//            return p;
//        }
//
//        p[0] = '\0';
//        int arr[2] = { 0 };
//        for (int j = 0; j < numRows; j++)
//        {
//            if (j == 0 || j == numRows - 1)
//            {
//                arr[0] = 2 * (numRows - 1);
//                for (int i = j; i < len;)
//                {
//                    strncat(p, &s[i], 1);
//                    if (arr[0])
//                    {
//                        i += arr[0];
//                    }
//                    else
//                    {
//                        i += 1;
//                    }
//                }
//            }
//            else
//            {
//                int num = 0;
//                arr[0] = 2 * (numRows - 1 - j);
//                arr[1] = 2 * j;
//                for (int i = j; i < len;)
//                {
//
//                    strncat(p, &s[i], 1);
//                    if (num % 2 == 0)
//                    {
//                        i += arr[0];
//                        num++;
//                    }
//                    else
//                    {
//                        i += arr[1];
//                        num++;
//                    }
//                }
//            }
//
//
//
//        }
//    }
//    return p;
//}

//
//#include<string.h>
//char* convert(char* s, int numRows) {
//    int len = strlen(s);
//    char* p = (char*)calloc(len + 1, 1);
//    if (p != NULL)
//    {
//        if (len < numRows || numRows == 1)
//        {
//            strncat(p, s, len);
//            return p;
//        }
//
//        p[0] = '\0';
//        int arr[2] = { 0 };
//        for (int j = 0; j < numRows; j++)
//        {
//            int num = 0;
//            arr[0] = 2 * (numRows - 1 - j);
//            arr[1] = 2 * j;
//            for (int i = j; i < len;)
//            {
//                strncat(p, &s[i], 1);
//                if (arr[0] == 0)
//                {
//                    num = 1;
//                }
//                if (num % 2 == 0)
//                {
//                    i += arr[0];
//                    num++;
//                }
//                else
//                {
//                    i += arr[1];
//                    num++;
//                }
//                if (j == 0 || j == numRows - 1)
//                {
//                    num++;
//                }
//            }
//        }
//    }
//    return p;
//}

//翻转整数
/*
int reverse(int x){
    long long  n=0;
    while(x)
    {
        n=n*10+x%10;
        x=x/10;
    }
    if(n<-pow(2,31)||n>pow(2,31)-1)
        return 0;
    return n;
}
*/
//
//int reverse(int x) {
//    long long  n = 0;
//    while (x)
//    {
//        if (n * 10 + x % 10 < -pow(2, 31) || n * 10 + x % 10 > pow(2, 31) - 1)
//            return 0;
//        else
//            n = n * 10 + x % 10;
//        x = x / 10;
//    }
//    return n;
//}

//判断回文数
//int isPalindrome(int x) {
//    if (x < 0)
//        return 0;
//    int a = 0;
//    int ret = x;
//    while (x)
//    {
//        a++;
//        x /= 10;
//    }
//    for (int i = 0; i < a / 2; i++)
//    {
//        int ret1 = pow(10, i);
//        int ret2 = pow(10, a - i - 1);
//        //printf("%d       %d   ",ret1,ret2);
//        int n1 = (ret / ret1) % 10;
//        int n2 = (ret / ret2) % 10;
//        //printf("%d %d",n1,n2);
//        if (n1 == n2)
//            continue;
//        else
//            return 0;
//    }
//    return 1;
//}


//罗马转整数
//#include<string.h>
//int romanToInt(char* s) {
//    int arr[] = { 1,5,10,50,100,500,1000 };
//    char c[] = "IVXLCDM";
//    int index[16] = { 0 };
//    int a = 0;
//
//
//    for (int i = 0; i < strlen(s); i++)
//    {
//
//        for (int j = 0; j < strlen(c); j++)
//        {
//            if (c[j] == s[i])
//                index[i] = j;
//        }
//
//        //printf("%d ",index[i]);
//    }
//    int flag = 1;
//    for (int i = 0; i < strlen(s); i++)
//    {
//        flag = 1;
//        if (i == strlen(s) - 1)
//        {
//            ;
//        }
//        else if (index[i] < index[i + 1])
//        {
//            flag = -1;
//        }
//        //printf("%d ",flag);
//        //printf("%d ",arr[index[i]]);
//
//        a += flag * arr[index[i]];
//        //printf("%d ",a);
//    }
//
//    return a;
//
//}


//整数转罗马

#include<string.h>
#include<math.h>
char* intToRoman(int num) {
    char* a[] = { "IV","IX","XL","XC","CD","CM" };
    char* b[] = { "V","L","D" };
    char* c[] = { "I","X","C","M" };
    char* p = (char*)calloc(40, 4);
    p[0] = '\0';
    int i = 0;
    int ret = num;
    while (ret)
    {
        i++;
        ret /= 10;
    }
    i--;
    while (i >= 0)
    {
        int n = pow(10, i);//3
        int j = (num / n) % 10;
        if (j == 4 && i < 3)
        {
            strcat(p, a[i * 2]);
        }
        else if (j == 9 && i < 3)
        {
            strcat(p, a[i * 2 + 1]);
        }
        else
        {
            if (j >= 5)
            {
                strcat(p, b[i]);
                j -= 5;
            }

            while (j)
            {
                strcat(p, c[i]);
                j--;
            }
        }
        i--;
    }
    return p;


}